package com.mlamp.递归;

public class 二叉树的最大深度 {
    public static void main(String[] args) {
        二叉树的最大深度 instance = new 二叉树的最大深度();
        //构造树
        TNode root = new TNode(3);
        root.left = new TNode(9);
        TNode t7 = new TNode(7);
        t7.left = new TNode(1000);
        TNode t20 = new TNode(20, new TNode(15), t7);
        root.right = t20;
        int maxDepth = instance.maxDepth(root);
        System.out.println("maxDepth: " + maxDepth);
        maxDepth = instance.maxDepthB(root);
        System.out.println(maxDepth);
    }


    public int maxDepth1(TNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth1(root.left), maxDepth(root.right)) + 1;
    }


    /**
     * 递归计算数深度
     *
     * @param root
     * @return
     */

    public int maxDepthB(TNode root) {
        if (root == null) return 0;
        return Math.max(maxDepthB(root.left), maxDepthB(root.right)) + 1;
    }

    public int maxDepthC(TNode root) {
        if (root == null) return 0;
        return Math.max(maxDepthC(root.left), maxDepthC(root.right)) + 1;
    }


    public int maxDepth3(TNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth3(root.left), maxDepth3(root.right)) + 1;
    }


    public int maxDepth(TNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        /**
         * maxDepth(9) + 1 + maxDepth(20)
         * = (maxDepth(null) + 1 + maxDepth(null)) + 1 + (maxDepth(15) + 1 + maxDepth(7))
         * = (0 + 1 + 0) + 1 + (maxDepth(null) + 1 + maxDepth(null)) + 1 + (maxDepth(null) + 1 + maxDepth(null))
         *  = 1 + 1 + 1 + 1
         *  = 4
         */
    }


    private static final class TNode {
        int val;
        TNode left;
        TNode right;

        public TNode() {

        }

        public TNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }

        public TNode(int value, TNode left, TNode right) {
            this.val = value;
            this.left = left;
            this.right = right;
        }
    }
}
